(1) Field of the Invention
The present invention relates to a variable length code decoding apparatus which decodes a bit stream including a code word that is variable-length-coded data.
(2) Description of the Related Art
In recent years, significant progress has been made in the development of moving picture compressing and coding techniques. Such techniques are being practically applied in fields such as broadcasting, communication and storage. Variable length coding is a moving picture compressing and coding technique capable of enhancing coding efficiency by varying code lengths according to the occurrence frequency of a value to be coded. In decoding variable-length-coded data (hereinafter referred to as a “code word”), since the code lengths of code words included in a bit stream differ from each other, the position of a given code word cannot be confirmed. Therefore, it is necessary to decode code words in sequence starting from the beginning of the bit stream.
As a variable length code decoding apparatus which decodes a variable-length-coded code word, for example, the variable length code decoding apparatus described in Japanese Patent No. 3341962 (JP 3341962) is known.
FIG. 1 is a diagram showing a configuration of a conventional variable length code decoding apparatus described in JP 3341962. The variable length code decoding apparatus 80 shown in FIG. 1 includes an input terminal 805, lookup tables 820 and 830, and multiplexers 840 and 841.
An n-bit bit stream (where n is a natural number) is inputted to the input terminal 805. m number of MSBs of the bit stream is inputted to the lookup table 820, while k number of LSBs are inputted to the lookup table 830 (where m and k are natural numbers and 0≦m≦n, 0≦k≦n).
The lookup tables 820 and 830 store tables including code lengths indicating bit lengths of code words respectively corresponding to addresses and code values that are data obtained by decoding code words. It should be noted that the tables stored in the lookup tables 820 and 830 are tables which separate the table of code lengths and code values corresponding to code words in order to prevent overlapping of addresses corresponding to code words, thereby enabling parallel-decoding of code words.
The respective lookup tables 820 and 830 use inputted bits as an address and output a code length indicating a bit length of a code word and a code value that is data obtained by decoding a code word which are stored at the designated address. Furthermore, the lookup table 820 outputs a decode signal indicating whether the lookup table 820 has successfully decoded the code word. A decode signal of “0” indicates that the lookup table 820 has successfully decoded the variable length code. A decode signal of “1” indicates that decoding of the variable length code by the lookup table 820 was not successful.
The code values and the decode signals outputted from the lookup tables 820 and 830 are inputted to the multiplexer 840. When the decode signal is “0”, the multiplexer 840 outputs the code value outputted by the lookup table 820, and when the decode signal is “1”, the multiplexer 840 outputs the code value outputted by the lookup table 830.
The code lengths and the decode signals outputted from the lookup tables 820 and 830 are inputted to the multiplexer 841. When the decode signal is “0”, the multiplexer 841 outputs the code length outputted by the lookup table 820, and when the decode signal is “1”, the multiplexer 840 outputs the code length outputted by the lookup table 830.
According to the configuration described above, the two lookup tables 820 and 830 enable the conventional variable length code decoding apparatus 80 to decode variable-length-coded code words in parallel.
In addition, with the conventional variable length code decoding apparatus 80, one code word is decoded per each predetermined cycle. Next, using the code length of a decoded code word, a process for extracting a bit string from the beginning of an undecoded bit stream is performed. In subsequent cycles, code words are sequentially decoded from the beginning of the bit stream by repetitively performing the decoding process and the extraction process.
However, it is desired that variable length code decoding apparatuses perform decoding at higher speeds. In the conventional variable length code decoding apparatus, the time required for decoding one code word is the sum of the time required for collating the code word by the lookup tables 820 and 830 and the time required for extracting a bit string from the beginning of the undecoded bit stream using the code length of the decoded code word.
It should be noted that the object of the variable length code decoding apparatus described in JP 3341962 is to reduce the capacities of the lookup tables 820 and 830 and no significant advantage may be gained with respect to increasing speed. For example, the operation speed of the variable length code decoding apparatus described in JP 3341962 does not significantly differ from a case of a single lookup table with a hard-wired configuration which is operated at an optimized operation speed. (See. e.g., pp. 6-10, FIG. 2, and the like, of JP3341962)